package LeetCode.tree;

public class LC_110 {
    public boolean isBalanced(TreeNode root) {  //时间复杂度O(n^2)
        if(root == null){
            return true;
        }
        if(Math.abs(calculateDepth(root.left)) - Math.abs(calculateDepth(root.right)) > 1){
            return false;
        }
        boolean leftTree = isBalanced(root.left);
        boolean rightTree = isBalanced(root.right);
        return leftTree && rightTree;
    }
    public int calculateDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int leftHeight = calculateDepth(root.left);
        int rightHeight = calculateDepth(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }
//    public boolean isBalanced(TreeNode root) {  //时间复杂度O(n)
//        return calculateDepth(root) >= 0;
//    }
//    public int calculateDepth(TreeNode root) {
//        if(root == null){
//            return 0;
//        }
//        if(root.left == null && root.right == null){
//            return 1;
//        }
//        int leftHeight = calculateDepth(root.left);
//        int rightHeight = calculateDepth(root.right);
//        if(leftHeight >= 0 && rightHeight >= 0 && (Math.abs(leftHeight-rightHeight) > 1)){
//            return Math.max(leftHeight,rightHeight) + 1;
//        } else {
//            return -1;
//        }
//    }
}
